package com.datastructure.tree;

import javax.swing.event.TreeExpansionEvent;

/**
 * 二叉树管理类
 *
 * @author luhd
 * @date 2022-11-02
 */
public class BinaryTree {

    /**
     * 新建代表整棵树的节点
     */
    TreeNode root;

    /**
     * 非递归构建有序二叉树
     */
    public void insert(Integer value){
        // 新建一个节点
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            root = newNode;
        } else {
            TreeNode current = root;

            TreeNode parentNode;
            while(true) {
                parentNode = current;
                if (newNode.getValue() > current.getValue()) {
                    current = current.getRightTreeNode();
                    if (current == null) {
                        parentNode.setRightTreeNode(newNode);
                        return;
                    }
                } else {
                    current = current.getLeftTreeNode();
                    if (current == null) {
                        parentNode.setLeftTreeNode(newNode);
                        return;
                    }
                }
            }
        }
    }

    /**
     * 递归构建有序二叉树
     */
    public TreeNode insert(TreeNode node,Integer value) {
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            return root = newNode;
        }
        if(newNode.getValue() > node.getValue()){
            if(node.getRightTreeNode() == null){
                node.setRightTreeNode(newNode);
                return root;
            }
            return insert(node.getRightTreeNode(),value);
        }else{
            if(node.getLeftTreeNode() == null){
                node.setLeftTreeNode(newNode);
                return root;
            }
            return insert(node.getLeftTreeNode(),value);
        }
    }

    //递归先序遍历
    public void preOrder(TreeNode node){
        if(node == null){
            return;
        }
        System.out.println(" "+node.getValue());
        preOrder(node.getLeftTreeNode());
        preOrder(node.getRightTreeNode());
    }
    //递归中序遍历
    public void midOrder(TreeNode node){
        if(node == null){
            return;
        }
        midOrder(node.getLeftTreeNode());
        System.out.println(" "+node.getValue());
        midOrder(node.getRightTreeNode());
    }
    //递归后序遍历
    public void lastOrder(TreeNode node){
        if(node == null){
            return;
        }
        lastOrder(node.getLeftTreeNode());
        lastOrder(node.getRightTreeNode());
        System.out.println(" "+node.getValue());
    }
}


















